import java.util.ArrayList;
import java.util.List;

class Solution {
    public static void main(String[] args){
        Solution solution = new Solution();
        List<String> and = solution.generateParenthesis(3);
        System.out.println(and);
    }
    public List<String> generateParenthesis(int n) {
        ArrayList<String> ans = new ArrayList<>();
        String curResult = "";
        int left = n,right = n;
        findPrint(left,right,curResult,ans,n);
        return ans;
    }

    private void findPrint(int left, int right, String curResult, ArrayList<String> ans, int n) {
        if (curResult.length() == n * 2) {
            ans.add(curResult);
            return;
        }
        if (left > 0) {
            curResult+="(";
            findPrint(--left,right,curResult,ans,n);
        }
        if (right > left) {
            curResult+=")";
            findPrint(left,--right,curResult,ans,n);
        }
    }
}
